
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1719. -- [Usaco2006 Jan] Roping the Field -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1719: [Usaco2006 Jan] Roping the Field</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>17&nbsp;&nbsp;<span class=green>Solved: </span>6<br>[<a href='submitpage.php?id=1719'>Submit</a>][<a href='problemstatus.php?id=1719'>Status</a>][<a href='bbs.php?id=1719'>Discuss</a>]</center><h2>Description</h2><div class=content>
Farmer John is quite the nature artist: he often constructs large
works of art on his farm. Today, FJ wants to construct a giant
"field web". FJ's field is large convex polygon with fences along
the boundary and fence posts at each of the N corners (1 <= N <=
150). To construct his field web, FJ wants to run as many ropes as
possible in straight lines between pairs of non-adjacent fence posts
such that no two ropes cross.

There is one complication: FJ's field is not completely usable.
Some evil aliens have created a total of G (0 <= G <= 100) grain
circles in the field, all of radius R (1 <= R <= 100,000). FJ is
afraid to upset the aliens, and therefore doesn't want the ropes
to pass through, or even touch the very edge of a grain circle.
Note that although the centers of all the circles are contained
within the field, a wide radius may make it extend outside of the
field, and both fences and fence posts may be within a grain circle.

Given the locations of the fence posts and the centers of the
circles, determine the maximum number of ropes that FJ can use to
create his field web.

FJ's fence posts and the circle centers all have integer coordinates
X and Y each of which is in the range 0..1,000,000.
</div><h2>Input</h2><div class=content>* Line 1: Three space-separated integers: N, G, and R

* Lines 2..N+1: Each line contains two space-separated integers that
        are the X,Y position of a fence post on the boundary of FJ's
        field.

* Lines N+2..N+G+1: Each line contains two space-separated integers
        that are the X,Y position of a circle's center inside FJ's
        field.

</div><h2>Output</h2><div class=content>* Line 1: A single integer that is the largest number of ropes FJ can
        use for his artistic creation.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 3 1<br />
6 10<br />
10 7<br />
9 1<br />
2 0<br />
0 3<br />
2 2<br />
5 6<br />
8 3<br />
<br />
INPUT DETAILS:<br />
<br />
A pentagonal field, in which all possible ropes are blocked by three<br />
grain circles, except for the rope between fenceposts 2 and 4.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
1<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1719'>Submit</a>][<a href='problemstatus.php?id=1719'>Status</a>][<a href='bbs.php?id=1719'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
